package binaryTree;

import org.junit.Test;

import java.util.Stack;

public class LeetCode_98 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    @Test
    public void test() {
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(-1);
//        root.right = new TreeNode(-1);

        System.out.println(isValidBST(root));


    }

    @Test
    public void test_1() {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        System.out.println(this.solution_3(root));

    }

    public class result{
        Integer MinValue;
        Integer MaxValue;
        boolean exist;

        public result(int minValue, int maxValue, boolean exist) {
            MinValue = minValue;
            MaxValue = maxValue;
            this.exist = exist;
        }
    }

    public boolean isValidBST(TreeNode root) {
        //return solution_1(root).exist;
//        return solution_2(root);
        return solution_3(root);
    }

    /**
     * 解法1：递归解决
     * @param root   根节点
     * @return true：存在，false：不存在
     */
    private result solution_1(TreeNode root) {
        if (root == null){
            return null;
        }
        //判断左子树
        result left = null;
        result right = null;
        if (root.left!= null){
            left = solution_1(root.left);
        }
        //判断右子树
        if (root.right!= null){
            right = solution_1(root.right);
        }
        //判断中间节点,取最小值和最大值
        Integer leftMin = (left == null)? null : left.MinValue;
        Integer leftMax = (left == null)? null : left.MaxValue;
        Integer rightMin = (right == null)? null : right.MinValue;
        Integer rightMax = (right == null)? null : right.MaxValue;
        boolean leftExist = (left == null)? true : left.exist;
        boolean rightExist = (right == null)? true : right.exist;
        Integer MinValue = min(min(leftMin,rightMin),root.val);
        Integer MaxValue = max(max(leftMax,rightMax),root.val);
        boolean exist = leftExist && rightExist && check(root.val, leftMax, rightMin);
        return new result(MinValue,MaxValue,exist);
    }

    /**
     * 解法2：非递归解决
     * @param root   根节点
     * @return true：存在，false：不存在
     */
    private boolean solution_2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        //1. 根入栈，根节点的所有左子树入栈
        stack.push(root);
        while(root.left!= null){
            stack.push(root.left);
            root = root.left;
        }
        //2. 进入循环，截止条件为栈空
        while(!stack.isEmpty()){
            //2.1 出栈
            TreeNode node = stack.pop();
            //2.2 判断是否符合搜索二叉树条件
            if (!checkNode(node)){
                return false;
            }
            //2.3 右子树入栈，若右子树存在，则将右子树的所有左节点入栈
            if (node.right!= null){
                stack.push(node.right);
                TreeNode right = node.right;
                while(right.left!= null){
                    stack.push(right.left);
                    right = right.left;
                }
            }
        }
        return true;
    }

    /**
     * 解法3：利用线索二叉树
     * @param root   根节点
     * @return true：存在，false：不存在
     */
    private boolean solution_3(TreeNode root){
        //1. 定义变量
        TreeNode tempNode = root;
        Integer tempVal=null;
        //2. 循环
        while(tempNode!=null){
            //2.1 左子树存在
            if (tempNode.left!= null){
                //2.1.1 找到左子树的最右节点
                TreeNode rightMax = findMax(tempNode);
                //2.1.2 判断最右节点情况
                if (rightMax.right == null){
                    rightMax.right = tempNode;
                    tempNode = tempNode.left;
                }else{
                    if (tempVal!= null && tempNode.val <= tempVal){
                        return false;
                    }else{
                        tempVal = tempNode.val;
                    }
                    rightMax.right = null;
                    tempNode = tempNode.right;
                }
            }else if (tempNode.right!= null){    //2.2 右子树存在
                if (tempVal!= null && tempNode.val <= tempVal){
                    return false;
                }else{
                    tempVal = tempNode.val;
                }
                tempNode = tempNode.right;
            }else{    //2.3 左右子树都不存在
                if (tempVal!= null && tempNode.val <= tempVal){
                    return false;
                }else{
                    tempVal = tempNode.val;
                }
                break;
            }
        }
        return true;
    }

    public TreeNode findMax(TreeNode root){
        TreeNode tempNode = root.left;
        if (tempNode.right == null || tempNode.right==root){
            return tempNode;
        }
        while(tempNode.right!=null && tempNode.right!=root){
            tempNode = tempNode.right;
        }
        return tempNode;
    }

    //判断是否满足条件（中比左子树最大更大，比右子树最小更小）
    public boolean checkNode(TreeNode root){
        Integer leftTreeMax = null , rightTreeMin = null;
        //左子树最大
        if (root.left!=null){
            TreeNode node = root.left;
            while(node.right!=null){
                node=node.right;
            }
            leftTreeMax = node.val;
        }
        //右子树更小
        if (root.right!=null){
            TreeNode node = root.right;
            while(node.left!=null){
                node=node.left;
            }
            rightTreeMin = node.val;
        }
        //判断条件
        if (leftTreeMax != null && root.val <= leftTreeMax ){
            return false;
        }
        if (rightTreeMin != null && root.val >= rightTreeMin ){
            return false;
        }
        return true;
    }

    public boolean check(Integer val,Integer leftMax,Integer rightMin) {

        if( leftMax == null && rightMin == null){
            return true;
        }
        if( leftMax == null && rightMin != null){
            return val < rightMin;
        }
        if ( leftMax != null && rightMin ==null ){
            return val > leftMax;
        }
        return val > leftMax && val < rightMin;
    }

    public Integer min(Integer a, Integer b){
        if (a==null && b==null){
            return null;
        }
        if(a == null && b != null){
            return b;
        }
        if (a!=null && b == null){
            return a;
        }
        return a < b? a : b;
    }

    public Integer max(Integer a, Integer b){
        if (a==null && b==null){
            return null;
        }
        if(a == null && b != null){
            return b;
        }
        if (a!=null && b == null){
            return a;
        }
        return a > b? a : b;
    }
}
